package com.wangzemin.leetcode.num92;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null || left >= right || left < 0) {
            return head;
        }
        ListNode virHeader = new ListNode();
        virHeader.next = head;

        ListNode revertPreNode = virHeader;
        ListNode revertFirstNode = revertPreNode.next;
        for (int i = 0; i < left - 1 && revertPreNode.next != null; i++) {
            revertPreNode = revertPreNode.next;
            revertFirstNode = revertFirstNode.next;
        }

        if (revertFirstNode == null) {
            return head;
        }

        ListNode revertLastNode = revertFirstNode;
        ListNode revertSufNode = revertLastNode.next;
        for (int i = 0; i < right - left && revertSufNode != null; i++) {
            revertLastNode = revertLastNode.next;
            revertSufNode = revertSufNode.next;
        }

        revertPreNode.next = null;
        revertLastNode.next = null;

        ListNode revertedList = revertList(revertFirstNode);

        revertPreNode.next = revertedList;
        while (revertedList.next != null) {
            revertedList = revertedList.next;
        }
        revertedList.next = revertSufNode;

        return virHeader.next;
    }

    private ListNode revertList(ListNode revertFirstNode) {
        if (revertFirstNode == null || revertFirstNode.next == null) {
            return revertFirstNode;
        }

        ListNode pre = null;
        ListNode cur = revertFirstNode;
        ListNode revertedHead = cur;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            revertedHead = cur;
            pre = cur;
            cur = next;
        }
        return revertedHead;
    }
}
